Casper CBC: Turán Oracle
Turán Oracle
With Turán's Theorem, we can get a lower bound of the size (not weight) of a clique.
Let$ Gbe any graph with$ nvertices, such that$ Gis$ K_{r+1}-free
that is, it has no clique of size$ r+1or greater.
Then the number of edges in$ Gis at most:
$ (r-1) / r * n^2 / 2
Let us say that we have$ eedges in our graph, and solve for$ r
$ e = (r-1) / r * n^2 / 2 nrryuya.icon > $ e \leq (r-1) / r * n^2 / 2
$ er = (r-1) * n^2 / 2
$ er = rn^2 / 2- n^2 / 2
$ er - rn^2 / 2= - n^2 / 2
$ r (e - n^2/2) = - n^2 / 2
$ r (n^2/2 - e) = n^2 / 2 nrryuya.icon > The inequiality turns here.
$ r = n^2 / (2(n^2/2 - e))
$ r = n^2 / (n^2 - 2e) nrryuya.icon > $ r \geq n^2 / (n^2 - 2e)
Thus, we can say that in a graph w/$ nnodes and$ eedges, there is at least a clique of size ceiling$ (n^2 / (n^2 - 2e))
Resources
ethereum/cbc-casper
CasperLabs
RChain
This should help us debug any issues with the safety oracle as now we aren't using a lower bound on the maximum clique size.
Runs turan oracle over the forkchoice everytime a new block is added (for now). The log output looks like follows:
This prevents the safety oracle from mistakenly finalizing in the cases where blocks that come after in sequence of a latest block in the justification of another latest block disagree with the estimate. The following diagram shows an example of this: (omitted)
The turan oracle is a type of clique oracle and one of the more conservative (and quick to execute) safety oracles. This should do for checking safety of blocks in Node v0.3. Note since disagreements have not been implemented there may be false positives on safety. A follow up PR implementing disagreements will come soon.